package com.chukun.interview.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author chukun
 * @version 1.0.0
 * @description 柱状图中最大的矩形
 * @createTime 2023年05月07日 22:59:00
 */
public class LargestRectangleArea {

    public static void main(String[] args) {
        int [] heights = new int[] {2,0,2};
        System.out.println(largestRectangleArea01(heights));
        System.out.println(largestRectangleArea02(heights));
    }

    /**
     * leetcode 84
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     *
     * 输入：heights = [2,1,5,6,2,3]
     * 输出：10
     *
     * 暴力求解法
     * @param heights
     * @return
     */
    public static int largestRectangleArea01(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length ; i++) {
            // 找左边最后 1 个大于等于 heights[i] 的下标
            int left = i;
            int currentHeight = heights[i];
            while (left >0 && heights[left -1] >= currentHeight) {
                left --;
            }
            int right = i;
            while (right < heights.length -1 && heights[right + 1] >= currentHeight) {
                right ++;
            }
            maxArea = Math.max(maxArea, currentHeight * (right - left + 1));
        }
        return maxArea;
    }

    public static int largestRectangleArea02(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}
